#include<stdio.h>
#include<stdlib.h>
typedef char ElemType;
// 定义线索二叉树的节点结构
typedef struct ThreadNode {
    ElemType data; // 节点存储的数据
    struct ThreadNode *left; // 左指针：指向左孩子或前驱
    struct ThreadNode *right; // 右指针：指向右孩子或后继
    int ltag; // 左标志：0 表示左孩子，1 表示前驱线索
    int rtag; // 右标志：0 表示右孩子，1 表示后继线索
} ThreadNode,*ThreadTree;
    
char str[] = "ABDH##I##EJ###CF##G##";  // 根据前序遍历序列构造树，# 表示空
int index = 0;                           // 当前扫描到的字符位置
ThreadTree prev;

void createTree(ThreadTree*t){
  ElemType ch;
  ch=str[index++];
  if(ch=='#'){
    *t=NULL;
  }else{
    *t=(ThreadTree)malloc(sizeof(ThreadNode));
    (*t)->data=ch;
    createTree(&(*t)->left);
    if((*t)->left!=NULL){
      (*t)->ltag=0;
    }
    createTree(&(*t)->right);
    if((*t)->right!=NULL){
      (*t)->rtag=0;
    }
  }
}

//线索化
void threading(ThreadTree t){
  if(t!=NULL){
    threading(t->left);
    if(t->left==NULL){
      t->ltag=1;
      t->left=prev;
    }
    if(prev->right==NULL){
      prev->rtag=1;
      prev->right=t;
    }
    prev=t;
    threading(t->right);
  }
}

void inOrderThreading(ThreadTree *t,ThreadTree *h){
  *h=(ThreadTree)malloc(sizeof(ThreadNode));
  (*h)->ltag=0;
  (*h)->rtag=1;
  (*h)->right=*h;

  if(t==NULL){ 
    (*h)->left=*h;
  }else{
    (*h)->left=*t;
    prev=*h; 
    threading(*t);

    prev->right=*h;
    prev->rtag=1;

    (*h)->right=prev;
  }
}

//使用线索进行中序遍历
void inOrder(ThreadTree t){
  ThreadTree cur;
  cur=t->left;
  while(cur!=t){
    while(cur->ltag==0){
      cur=cur->left;
    }
    printf("%c ",cur->data);
    while(cur->rtag==1&&cur->right!=t){
      cur=cur->right;
      printf("%c ",cur->data);
    }
    cur=cur->right;
  }
}

int main(){
  ThreadTree T, head;
    createTree(&T);               // 创建原始二叉树
    inOrderThreading(&T, &head); // 执行线索化处理
    printf("中序遍历结果：");
    inOrder(head);                // 遍历线索二叉树
    return 0;
}